(car '(a b c d e))

(defun subst (x y z)
  (cond ((atom z)
         (cond ((eq z y) x)
               ('t z)))
        ('t (cons (subst x y (car z))
                  (subst x y (cdr z))))))

(subst 'm 'b '(a b (a b c) d))

(defun null. (x)
  (eq x '()))

(null. 'a)

(null. '())

(defun and. (x y)
  (cond (x (cond (y 't) ('t '())))
        ('t '())))

(and. (atom 'a) (eq 'a 'a))

(and. (atom 'a) (eq 'a 'b))

(defun not. (x)
  (cond (x '())
        ('t 't)))

(not (eq 'a 'a))

(not (eq 'a 'b))

(defun append. (x y)
  (cond ((null. x) y)
        ('t (cons (car x) (append. (cdr x) y)))))

(append. '(a b) '(c d))

(append. '() '(c d))

(defun pair. (x y)
  (cond ((and. (null. x) (null. y)) '())
        ((and. (not. (atom x)) (not. (atom y)))
         (cons (list (car x) (car y))
               (pair. (cdr x) (cdr y))))))

(pair. '(x y z) '(a b c))

(defun assoc. (x y)
  (cond ((eq (caar y) x) (cadar y))
        ('t (assoc. x (cdr y)))))

(assoc. 'x '((x a) (y b)))

(assoc. 'x '((x new) (x a) (y b)))

(defun eval. (e a)
  (cond
    ((atom e) (assoc. e a))
    ((atom (car e))
     (cond
       ((eq (car e) 'quote) (cadr e))
       ((eq (car e) 'atom) (atom (eval. (cadr e) a)))
       ((eq (car e) 'eq) (eq (eval. (cadr e) a)
                             (eval. (caddr e) a)))
       ((eq (car e) 'car) (car (eval. (cadr e) a)))
       ((eq (car e) 'cdr) (cdr (eval. (cadr e) a)))
       ((eq (car e) 'cons) (cons (eval. (cadr e) a)
                                 (eval. (caddr e) a)))
       ((eq (car e) 'cond) (evcon. (cdr e) a))
       ('t (eval. (cons (assoc. (car e) a)
                        (cdr e))
                  a))))
    ((eq (caar e) 'label)
     (eval. (cons (caddar e) (cdr e))
            (cons (list (cadar e) (car e)) a)))
    ((eq (caar e) 'lambda)
     (eval. (caddar e)
            (append. (pair. (cadar e) (evlis. (cdr e) a))
                     a)))))

(defun evcon. (c a)
  (cond ((eval. (caar c) a)
         (eval. (cadar c) a))
        ('t (evcon. (cdr c) a))))

(defun evlis. (m a)
  (cond ((null. m) '())
        ('t (cons (eval.   (car m) a)
                  (evlis. (cdr m) a)))))

; These are the example after the presentation of eval

(eval. 'x '((x a) (y b)))
;a

(eval. '(eq 'a 'a) '())
;t

(eval. '(cons x '(b c))
       '((x a) (y b)))
;(a b c)

(eval. '(cond ((atom x) 'atom)
              ('t 'list))
       '(( x '(a b))))
;list

(eval. '(f '(b c))
       '((f (lambda (x) (cons 'a x)))))
;becomes

(eval. '((lambda (x) (cons 'a x)) '(b c))
       '((f (lambda (x) (cons 'a x)))))
;(a b c)

(eval. '((label firstatom (lambda (x)
                            (cond ((atom x) x)
                                  ('t (firstatom (car x))))))
         y)
       '((y ((a b) (c d)))))

;becomes

;a


(eval. '((lambda (x y) (cons x (cdr y)))
         'a
         '(b c d))
         '())
;becomes

;(a c d)

(eval. '((lambda () 'bar)) '())

(eval. '(f) '((f (lambda() 'bar))))

(eval. '(f) '((f (lambda() '(lambda () 'foobar)))))
;(LAMBDA NIL 'FOOBAR)

(eval. '((f)) '((f (lambda() '(lambda () 'foobar)))))
;nil

(eval. '(((f))) '((f (lambda() '(lambda () 'foobar)))))
;NIL

(eval. '(f g) '((f (lambda (x) x)) (g (lambda () 'foo))))
;(LAMBDA NIL 'FOO)

(eval. '(f g) '((f (lambda (x) (x))) (g (lambda () 'foo))))
;FOO

(eval. '(f (lambda() 'foo)) '((f (lambda (x) (x)))))
;*** - Program stack overflow. RESET

(eval. '(f '(lambda() 'foo)) '((f (lambda (x) (x)))))
;FOO

(eval. '((label subst (lambda (x y z)
                          (cond ((atom z)
                                 (cond ((eq z y) x)
                                       ('t z)))
                                ('t (cons (subst x y (car z))
                                          (subst x y (cdr z)))))))
         'm
         'b
         '(a b (a b c) d))
       '())
;(a m (a m c) d))

(eval. '(subst 'm 'b '(a b (a b c) d))
       '((subst  (lambda (x y z)
                          (cond ((atom z)
                                 (cond ((eq z y) x)
                                       ('t z)))
                                ('t (cons (subst x y (car z))
                                          (subst x y (cdr z)))))))))

;(a m (a m c) d))


(eval. '((label subset (lambda (keys lat)
                           (cond ((null. keys) 't)
                                 ((memq. (car keys) lat) (subset? (cdr keys) lat))
                                 ('t '()))))
         '(b d)
         '(a b c d e))
       '())

(eval. '(map f '(a b))
       '((f (lambda (x) 'foo))
         (map (lambda (ff l)
                 (cond ((eq l '()) '())
                       ('t (cons (f (car l)) (map ff (cdr l)))))))))
;(FOO FOO)

(eval. '(map f '(a b))
       '((f (lambda (x) x))
         (map (lambda (ff l)
                 (cond ((eq l '()) '())
                       ('t (cons (f (car l)) (map ff (cdr l)))))))))
;(A B)

(eval. '(map f '((a) (b)))
       '((f (lambda (x) x))
         (map (lambda (ff l)
                 (cond ((eq l '()) '())
                       ('t (cons (f (car l)) (map ff (cdr l)))))))))
;((A) (B))

(eval. '(map f '((a) (b)))
       '((f (lambda (x) (car x)))
         (map (lambda (ff l)
                 (cond ((eq l '()) '())
                       ('t (cons (f (car l)) (map ff (cdr l)))))))))
;(A B)

(eval. '(map f '((a) (b)))
       '((f (lambda (x) (cons 'foo x)))
         (map (lambda (ff l)
                 (cond ((eq l '()) '())
                       ('t (cons (f (car l)) (map ff (cdr l)))))))))
;((FOO A) (FOO B))

(eval. '(map f '((a) (b)))
       '((f (lambda (x) (cons 'foo x)))
         (map (lambda (ff l)
                 (cond ((eq l '()) '())
                       ('t (cons (f (car l)) (map ff (cdr l)))))))
         (filter (lambda (fff lll)
                 (cond ((eq lll '()) '())
                       ((fff (car lll)) (cons (car lll) (filter fff (cdr lll)))))
         ))
))
;((FOO A) (FOO B))

(eval. '(filter f '((a) (b)))
       '((f (lambda (x) 't))
         (map (lambda (ff l)
                 (cond ((eq l '()) '())
                       ('t (cons (f (car l)) (map ff (cdr l)))))))
         (filter (lambda (fff lll)
                 (cond ((eq lll '()) '())
                       ((fff (car lll)) (cons (car lll) (filter fff (cdr lll))))
                       ('t (filter fff (cdr lll)))
                 )
         ))
))

(eval. '(filter f '((a) (b)))
       '((f (lambda (x) '()))
         (map (lambda (ff l)
                 (cond ((eq l '()) '())
                       ('t (cons (f (car l)) (map ff (cdr l)))))))
         (filter (lambda (fff lll)
                 (cond ((eq lll '()) '())
                       ((fff (car lll)) (cons (car lll) (filter fff (cdr lll))))
                       ('t (filter fff (cdr lll)))
                 )
         ))
))

(eval. '(f '(a b))
       '((f (lambda (x) (eq (car x) (car (cdr x))) ))
         (map (lambda (ff l)
                 (cond ((eq l '()) '())
                       ('t (cons (f (car l)) (map ff (cdr l)))))))
         (filter (lambda (fff lll)
                 (cond ((eq lll '()) '())
                       ((fff (car lll)) (cons (car lll) (filter fff (cdr lll))))
                       ('t (filter fff (cdr lll)))
                 )
         ))
))

(eval. '(f '(a a))
       '((f (lambda (x) (eq (car x) (car (cdr x))) ))
         (map (lambda (ff l)
                 (cond ((eq l '()) '())
                       ('t (cons (f (car l)) (map ff (cdr l)))))))
         (filter (lambda (fff lll)
                 (cond ((eq lll '()) '())
                       ((fff (car lll)) (cons (car lll) (filter fff (cdr lll))))
                       ('t (filter fff (cdr lll)))
                 )
         ))
))

(eval. '(filter f '((a a) (a b) (c c) (c d)))
       '((f (lambda (x) (eq (car x) (car (cdr x))) ))
         (map (lambda (ff l)
                 (cond ((eq l '()) '())
                       ('t (cons (f (car l)) (map ff (cdr l)))))))
         (memq (lambda (key lat)
                 (cond ((null. lat) '())
                       ((eq key (car lat)) 't)
                       ('t (memq. key (cdr lat))))))
         (filter (lambda (fff lll)
                 (cond ((eq lll '()) '())
                       ((fff (car lll)) (cons (car lll) (filter fff (cdr lll))))
                       ('t (filter fff (cdr lll)))
                 )
         ))
))
;((A A) (C C))

(eval. '(memq 'a '(c b a))
       '((f (lambda (x) (eq (car x) (car (cdr x))) ))
         (map (lambda (ff l)
                 (cond ((eq l '()) '())
                       ('t (cons (f (car l)) (map ff (cdr l)))))))
         (memq (lambda (key lat)
                 (cond ((eq lat '()) '())
                       ((eq key (car lat)) 't)
                       ('t (memq key (cdr lat))))))
         (filter (lambda (fff lll)
                 (cond ((eq lll '()) '())
                       ((fff (car lll)) (cons (car lll) (filter fff (cdr lll))))
                       ('t (filter fff (cdr lll)))
                 )
         ))
))

(eval. '(memq 'a '(c b))
       '((f (lambda (x) (eq (car x) (car (cdr x))) ))
         (map (lambda (ff l)
                 (cond ((eq l '()) '())
                       ('t (cons (f (car l)) (map ff (cdr l)))))))
         (memq (lambda (key lat)
                 (cond ((eq lat '()) '())
                       ((eq key (car lat)) 't)
                       ('t (memq key (cdr lat))))))
         (filter (lambda (fff lll)
                 (cond ((eq lll '()) '())
                       ((fff (car lll)) (cons (car lll) (filter fff (cdr lll))))
                       ('t (filter fff (cdr lll)))
                 )
         ))
))
;NIL

(eval. '(memq 'a '(c b))
       '((f (lambda (x) (eq (car x) (car (cdr x))) ))
         (map (lambda (ff l)
                 (cond ((eq l '()) '())
                       ('t (cons (f (car l)) (map ff (cdr l)))))))
         (memq (lambda (key lat)
                 (cond ((eq lat '()) '())
                       ((eq key (car lat)) 't)
                       ('t (memq key (cdr lat))))))
         (filter (lambda (fff lll)
                 (cond ((eq lll '()) '())
                       ((fff (car lll)) (cons (car lll) (filter fff (cdr lll))))
                       ('t (filter fff (cdr lll)))
                 )
         ))
))

(eval. '(memq 'a '(c b))
       '((f (lambda (x) (eq (car x) (car (cdr x))) ))
         (map (lambda (ff l)
                 (cond ((eq l '()) '())
                       ('t (cons (f (car l)) (map ff (cdr l)))))))
         (memq (lambda (key lat)
                 (cond ((eq lat '()) '())
                       ((eq key (car lat)) 't)
                       ('t (memq key (cdr lat))))))
         (subset (lambda (keys lat)
                 (cond ((eq keys '()) 't)
                       ((memq (car keys) lat) (subset (cdr keys) lat))
                       ('t '()))))
         (filter (lambda (fff lll)
                 (cond ((eq lll '()) '())
                       ((fff (car lll)) (cons (car lll) (filter fff (cdr lll))))
                       ('t (filter fff (cdr lll)))
                 )
         ))
))

(eval. '(subset '(a) '(c b))
       '((f (lambda (x) (eq (car x) (car (cdr x))) ))
         (map (lambda (ff l)
                 (cond ((eq l '()) '())
                       ('t (cons (f (car l)) (map ff (cdr l)))))))
         (memq (lambda (key lat)
                 (cond ((eq lat '()) '())
                       ((eq key (car lat)) 't)
                       ('t (memq key (cdr lat))))))
         (subset (lambda (keys lat)
                 (cond ((eq keys '()) 't)
                       ((memq (car keys) lat) (subset (cdr keys) lat))
                       ('t '()))))
         (filter (lambda (fff lll)
                 (cond ((eq lll '()) '())
                       ((fff (car lll)) (cons (car lll) (filter fff (cdr lll))))
                       ('t (filter fff (cdr lll)))
                 )
         ))
))

(eval. '(subset '(a b) '(a c b d))
       '((f (lambda (x) (eq (car x) (car (cdr x))) ))
         (map (lambda (ff l)
                 (cond ((eq l '()) '())
                       ('t (cons (f (car l)) (map ff (cdr l)))))))
         (memq (lambda (key lat)
                 (cond ((eq lat '()) '())
                       ((eq key (car lat)) 't)
                       ('t (memq key (cdr lat))))))
         (subset (lambda (keys lat)
                 (cond ((eq keys '()) 't)
                       ((memq (car keys) lat) (subset (cdr keys) lat))
                       ('t '()))))
         (filter (lambda (fff lll)
                 (cond ((eq lll '()) '())
                       ((fff (car lll)) (cons (car lll) (filter fff (cdr lll))))
                       ('t (filter fff (cdr lll)))
                 )
         ))
))

(eval. '(subset '(a b) '(a c b d))
 '((db 
    (((content) (tags))
     ((to be or not to be) (quote shakespeare tags))
     ((final record) (eof))))
   (f (lambda (x) (eq (car x) (car (cdr x))) ))
   (map 
    (lambda (ff l)
     (cond ((eq l '()) '())
            ('t (cons (f (car l)) (map ff (cdr l)))))))
   (memq 
    (lambda (key lat)
     (cond ((eq lat '()) '())
           ((eq key (car lat)) 't)
           ('t (memq key (cdr lat))))))
   (subset 
    (lambda (keys lat)
     (cond ((eq keys '()) 't)
           ((memq (car keys) lat) (subset (cdr keys) lat))
           ('t '()))))
   (filter 
    (lambda (fff lll)
     (cond ((eq lll '()) '())
           ((fff (car lll)) (cons (car lll) (filter fff (cdr lll))))
           ('t (filter fff (cdr lll))))))
  )
)

(eval. '(subset '(a b) '(a c b d))
 '((db 
    (((content) (tags))
     ((to be or not to be) (quote shakespeare tags))
     ((final record) (eof))))
   (f (lambda (x) (eq (car x) (car (cdr x))) ))
   (tag-query
    (lambda (tags db)
     (filter '(lambda (item) (tagsq tags item)) db)))
   (tagsq
    (lambda (query-tags item)
     (subset (query-tags) (cdr item))))
   (map 
    (lambda (ff l)
     (cond ((eq l '()) '())
            ('t (cons (f (car l)) (map ff (cdr l)))))))
   (memq 
    (lambda (key lat)
     (cond ((eq lat '()) '())
           ((eq key (car lat)) 't)
           ('t (memq key (cdr lat))))))
   (subset 
    (lambda (keys lat)
     (cond ((eq keys '()) 't)
           ((memq (car keys) lat) (subset (cdr keys) lat))
           ('t '()))))
   (filter 
    (lambda (fff lll)
     (cond ((eq lll '()) '())
           ((fff (car lll)) (cons (car lll) (filter fff (cdr lll))))
           ('t (filter fff (cdr lll))))))
  )
)


(eval. '(tag-query '(tags) db)
 '((db 
    (((content) (tags))
     ((to be or not to be) (quote shakespeare tags))
     ((final record) (eof))))
   (f (lambda (x) (eq (car x) (car (cdr x))) ))
   (tag-query
    (lambda (tags db)
     (filter '(lambda (item) (tagsq tags item)) db)))
   (tagsq
    (lambda (query-tags item)
     (subset (query-tags) (cdr item))))
   (map 
    (lambda (ff l)
     (cond ((eq l '()) '())
            ('t (cons (f (car l)) (map ff (cdr l)))))))
   (memq 
    (lambda (key lat)
     (cond ((eq lat '()) '())
           ((eq key (car lat)) 't)
           ('t (memq key (cdr lat))))))
   (subset 
    (lambda (keys lat)
     (cond ((eq keys '()) 't)
           ((memq (car keys) lat) (subset (cdr keys) lat))
           ('t '()))))
   (filter 
    (lambda (fff lll)
     (cond ((eq lll '()) '())
           ((fff (car lll)) (cons (car lll) (filter fff (cdr lll))))
           ('t (filter fff (cdr lll))))))
  )
)

(eval. '(tagsq '(foo) (car db))
 '((db 
    (((content) (tags))
     ((to be or not to be) (quote shakespeare tags))
     ((final record) (eof))))
   (f (lambda (x) (eq (car x) (car (cdr x))) ))
   (tag-query
    (lambda (tags db)
     (filter '(lambda (item) (tagsq tags item)) db)))
   (tagsq
    (lambda (query-tags item)
     (subset query-tags (cdr item))))
   (map 
    (lambda (ff l)
     (cond ((eq l '()) '())
            ('t (cons (f (car l)) (map ff (cdr l)))))))
   (memq 
    (lambda (key lat)
     (cond ((eq lat '()) '())
           ((eq key (car lat)) 't)
           ('t (memq key (cdr lat))))))
   (subset 
    (lambda (keys lat)
     (cond ((eq keys '()) 't)
           ((memq (car keys) lat) (subset (cdr keys) lat))
           ('t '()))))
   (filter 
    (lambda (fff lll)
     (cond ((eq lll '()) '())
           ((fff (car lll)) (cons (car lll) (filter fff (cdr lll))))
           ('t (filter fff (cdr lll))))))
  )
)

(eval. '(tag-query '(tags) db)
 '((db 
    (((content) (tags))
     ((to be or not to be) (quote shakespeare tags))
     ((final record) (eof))))
   (f (lambda (x) (eq (car x) (car (cdr x))) ))
   (tag-query
    (lambda (tags db)
     (filter '(lambda (item) (tagsq tags item)) db)))
   (tagsq
    (lambda (query-tags item)
     (subset query-tags (cdr item))))
   (map 
    (lambda (ff l)
     (cond ((eq l '()) '())
            ('t (cons (f (car l)) (map ff (cdr l)))))))
   (memq 
    (lambda (key lat)
     (cond ((eq lat '()) '())
           ((eq key (car lat)) 't)
           ('t (memq key (cdr lat))))))
   (subset 
    (lambda (keys lat)
     (cond ((eq keys '()) 't)
           ((memq (car keys) lat) (subset (cdr keys) lat))
           ('t '()))))
   (filter 
    (lambda (fff lll)
     (cond ((eq lll '()) '())
           ((fff (car lll)) (cons (car lll) (filter fff (cdr lll))))
           ('t (filter fff (cdr lll))))))
  )
)

(eval. '(tag-query '(foo) db)
 '((db 
    (((content) (foo))
     ((more content) (bar))
     ((yet more content) (foo bar))
     ))
   (tag-query
    (lambda (tags db)
     (filter '(lambda (item) (tagsq tags item)) db)))
   (tagsq
    (lambda (query-tags item)
     (subset query-tags (car (cdr item)))))
   (memq 
    (lambda (key lat)
     (cond ((eq lat '()) '())
           ((eq key (car lat)) 't)
           ('t (memq key (cdr lat))))))
   (subset 
    (lambda (keys lat)
     (cond ((eq keys '()) 't)
           ((memq (car keys) lat) (subset (cdr keys) lat))
           ('t '()))))
   (filter 
    (lambda (f l)
     (cond ((eq l '()) '())
           ((f (car l)) (cons (car l) (filter f (cdr l))))
           ('t (filter f (cdr l))))))
   (map 
    (lambda (f l)
     (cond ((eq l '()) '())
            ('t (cons (f (car l)) (map f (cdr l)))))))
   (subst  
    (lambda (x y z)
     (cond ((atom z)
      (cond ((eq z y) x)
             ('t z)))
      ('t (cons (subst x y (car z))
                (subst x y (cdr z)))))))
  )
)

(eval. '(tag-query '(foo) db)
 '((db 
    (((content) (foo))
     ((more content) (bar))
     ((yet more content) (foo bar))
     ))
   (tag-query
    (lambda (tags db)
     (filter '(lambda (item) (tagsq tags item)) db)))
   (tagsq
    (lambda (query-tags item)
     (subset query-tags (car (cdr item)))))
   (memq 
    (lambda (key lat)
     (cond ((eq lat '()) '())
           ((eq key (car lat)) 't)
           ('t (memq key (cdr lat))))))
   (subset 
    (lambda (keys lat)
     (cond ((eq keys '()) 't)
           ((memq (car keys) lat) (subset (cdr keys) lat))
           ('t '()))))
   (filter 
    (lambda (f l)
     (cond ((eq l '()) '())
           ((f (car l)) (cons (car l) (filter f (cdr l))))
           ('t (filter f (cdr l))))))
   (map 
    (lambda (f l)
     (cond ((eq l '()) '())
            ('t (cons (f (car l)) (map f (cdr l)))))))
   (subst  
    (lambda (x y z)
     (cond ((atom z)
      (cond ((eq z y) x)
             ('t z)))
      ('t (cons (subst x y (car z))
                (subst x y (cdr z)))))))
  )
)

(defparameter a
 '((db 
    (((content) (foo))
     ((more content) (bar))
     ((yet more content) (foo bar))
     ))
   (tag-query
    (lambda (tags db)
     (filter '(lambda (item) (tagsq tags item)) db)))
   (tagsq
    (lambda (query-tags item)
     (subset query-tags (car (cdr item)))))
   (memq 
    (lambda (key lat)
     (cond ((eq lat '()) '())
           ((eq key (car lat)) 't)
           ('t (memq key (cdr lat))))))
   (subset 
    (lambda (keys lat)
     (cond ((eq keys '()) 't)
           ((memq (car keys) lat) (subset (cdr keys) lat))
           ('t '()))))
   (filter 
    (lambda (f l)
     (cond ((eq l '()) '())
           ((f (car l)) (cons (car l) (filter f (cdr l))))
           ('t (filter f (cdr l))))))
   (map 
    (lambda (f l)
     (cond ((eq l '()) '())
            ('t (cons (f (car l)) (map f (cdr l)))))))
   (subst  
    (lambda (x y z)
     (cond ((atom z)
      (cond ((eq z y) x)
             ('t z)))
      ('t (cons (subst x y (car z))
                (subst x y (cdr z)))))))
  )
)

